1. Technical Field
The invention is related to image segmentation, and in particular, to a technique for identifying and extracting objects of interest in images through a minimization of global-local energy with respect to a global image data likelihood potential.
2. Related Art
Automatic extraction or segmentation of objects of interest from arbitrary still images as a function of foreground/background separation is a fundamental problem in computer vision. A number of conventional schemes have attempted to address this problem.
For example, one popular approach is to formulate the segmentation problem as an energy minimization problem. This general approach can be roughly categorized into one of two general categories: variational energy minimization, which usually involves solving a partial differential equation (PDE), and graph energy minimization which minimizes an energy functional using conventional graph-cut algorithms.
Image segmentation as a function of variational energy minimization is typically based on the conventional concept of “active contours.” In general, the energy functionals of such techniques are usually formulated on region boundary curves and/or over regions partitioned by the boundary curves. Unfortunately, in practice, energy functionals based purely on image gradient information often get stuck in local optima, especially when there are many spurious edges in the image. As a result, image segmentation is either degraded, or fails completely. On the other hand, conventional techniques which use intensity, color and texture distributions of the image pixels over the regions to formulate the energy functional can largely overcome this problem.
Consequently, better energy formulations can be achieved by combining the edge information and the feature distribution of the image pixels. The minimization of this type of variational energy has evolved from the traditional finite difference method (FDM) and the traditional finite element method (FEM) to the more advanced “level-set” methods used in a several conventional image segmentation techniques.
A large amount of work has been done on the implementation of conventional level-set methods to reduce the computation involved during the evolution of the implicit level-set surface so as to increase the efficiency of such techniques. Conventional examples of such techniques include “narrow-band level-set” methods, methods involving level-set without re-initialization, and methods involving fast level-set implementation without the necessity of solving PDEs. In general, each of these more efficient level-set algorithms takes advantage of the property of the signed distance function, which is usually adopted as implicit level-set functions for use in solving the image segmentation problem.
Alternately, formulating the problem of image segmentation as an energy minimization (or a posterior distribution maximization) to be solved by graph cut is justified by the Markov Random Field (MRF) theory. A number of conventional graph-cut image segmentation techniques have been proposed in recent years to provide for object extraction from images.
For example, one such conventional technique involves interactive object extraction. A related technique, referred to as the “iterative Grab-cut system,” adopts an efficient min-cut/max-flow algorithm to minimize the energy function. This min-cut/max-flow algorithm is guaranteed to find the global optimal for certain types of energy functions which satisfy the property that they are functions of binary variables, submodular, and can be written as the sum of terms involving at most three variables at a time. For energy functions with multi-label variables, approximate solutions can be obtained by applying conventional algorithms which utilize a sequence of binary moves such as alpha-expansion, alpha-beta swap and k-jumps, etc. Although there are efficient polynomial time algorithms for min-cut/max-flow algorithms, the types of energy functions that can be minimized by these algorithms are generally limited. Examples of more general but less efficient conventional algorithms, which can sample from arbitrary posterior distributions and thus can minimize a more general set of energy functions, include the “Swendsen-Wang cut” and the “generalized m-way Swendsen-Wang cut.”
In general, both the variational energy minimization approach and the graph energy minimization approach share the same basic methodology: formulating an objective energy function and solving the resulting optimization problem. The basic differences between the two techniques involve the different optimization strategies adopted by each technique. For example, variational energy minimization based techniques can typically be converted to a PDE and solved by FDM, FEM and level-set, while the graph energy minimization based techniques can be solved by any of a number of min-cut/max-flow algorithms, including the aforementioned Swendsen-Wang cut. The particular type of optimization scheme that is best suited for a particular technique is usually determined by the type of objective function involved. Further, the objective function is also a main factor determining the quality of the segmentation results.